class Solution:
    """
    方法：使用栈来验证括号的有效性。遍历字符串，遇到左括号入栈，遇到右括号时检查栈顶元素是否匹配，最后检查栈是否为空。
    
    Args:
        s: str, 包含括号的字符串
        
    Returns:
        bool: 如果括号有效返回True，否则返回False
        
    Time: O(n), 需要遍历整个字符串
    Space: O(n), 最坏情况下栈的大小为n/2
    """
    def isValid(self, s: str) -> bool:
        if len(s) % 2:
            return False
        mp = {')':'(', ']':'[', '}':'{'}
        st = []
        for c in s:
            if c not in mp: # c 是左括号
                st.append(c) # 入栈
            elif not st or st.pop() != mp[c]: # c 是右括号
                return False  # 没有左括号，或者左括号类型不对
        return not st # 所有左括号必须匹配完毕